#include "../Func.hpp"

int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
bool vis[110][110];
int n,m;
class Solution {
public:
    bool dfs(vector<string>& board, string word,int& pos,int x,int y)
    {
        if (pos == word.size()) return true;
        //标记当前位置
        vis[x][y] = true;
        for (auto&[p1,p2] : dir)
        {
            int a = p1 + x, b = p2 + x;
            if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && 
            board[a][b] == word[pos])
            {
                int old = pos;
                vis[a][b] = true;
                if (dfs(board,word,++pos,a,b)) return true;
                vis[a][b] = false;
                pos = old;
            } 
        }
        //取消标记当前位置
        vis[x][y] = false;
        return false;
    }
    bool exist(vector<string>& board, string word) {
        n = board.size(), m = board[0].size();
        int pos = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                vis[i][j] = true;
                if (board[i][j]==word[pos] && dfs(board,word,++pos,i,j)) return true;
                vis[i][j] = false;
                pos = 0; //找错了就重新找
            }
        }
        return false;
    }
};

int main()
{
    vector<string> board = {"XYZE","SFZS","XDEE"};
    string s("XYZZED");
    if (Solution().exist(board,s)) cout << "true" << endl;
    else cout  << "false" << endl;
    return 0;
}